/*************************************************************************
	> File Name: 042.接雨水.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 六  9/ 4 12:20:53 2021
 ************************************************************************/

//维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
//从左到右遍历数组，遍历到下标i时，如果栈内至少两个元素，记栈顶元素为top，top的下面一个元素为left，则一定有height[left] >= height[top]
//如果 height[i] > height[top]，则得到一个可以接雨水的区域，该区域的宽度为i - left - 1，高度为 min(height[left], height[i]) - height[top]

int trap(int *height, int heightSize) {
    if (heightSize == 0) return 0;

    int sta[heightSize], top = 0, ans = 0;
    for (int i = 0; i < heightSize; i++) {
        while (top && height[i] > height[sta[top - 1]]) {
            int top_index = sta[--top];
            if (top == 0) break; 
            int left = sta[top - 1];
            int curW = i - left - 1;
            int curH = fmin(height[left], height[i]) - height[top_index];
            ans += curW * curH;
        }
        sta[top++] = i;
    }
    return ans;
}
